"""
负权图dij
为每一个点u增加一个势能h[u]

对于边权我们设原来的边权为 w(u,v)
新的边权为 w'(u,v) = w(u,v) + h[u] - h[v]

如果我们这里有一条路径为
1 -> 2 -> 3 -> 4
原来的权值为 w(1,2) + w(2,3) + w(3,4)
更新后的权值为

w'(1,2) + w'(2,3) + w'(3,4)
= w(1,4) + h[1] - h[4]

所以如果我们将所有的权值 增到正数,那么就可以跑dij

"""